package pro.softzhang.algo.lc100;

import pro.softzhang.algo.common.ListNode;
import pro.softzhang.algo.common.Utils;

/**
 * 1
 *   3 4
 * 2
 */
public class LC160_IntersectionOfTwoLinkedLists {
    public static void main(String[] args) {
        ListNode headA = new ListNode(1);
        ListNode headB = new ListNode(2);
        ListNode n3 = new ListNode(3, new ListNode(4));
        headA.next = n3;
        headB.next = n3;
        Utils.printLinkedList(headA);
        Utils.printLinkedList(headB);
        ListNode intersection = new LC160_IntersectionOfTwoLinkedLists().getIntersectionNode(headA, headB);
        System.out.println(intersection == null ? null : intersection.val);
    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 统计各链表长度
        int aListSize = listSize(headA), bListSize = listSize(headB);
        int sizeDiff = aListSize - bListSize;
        ListNode p1 = aListSize >= bListSize ? headA : headB;
        ListNode p2 = aListSize >= bListSize ? headB : headA;
        for (int i = 0; i < Math.abs(sizeDiff); i++) {
            p1 = p1.next;
        }

        while (p1 != p2) {
            p1 = p1.next;
            p2 = p2.next;
        }

        return p1;
    }

    private int listSize(ListNode head) {
        int size = 0;
        while (head != null) {
            head = head.next;
            size++;
        }
        return size;
    }
}
